// 给定一个字符串数组chars，使用如下算法压缩
// 从空字符串s开始，对于chars中每个连续重复字符，
// 1，如果这一组长度为1，则将字符追加到s中，
// 2，如果这一组长度超过1，需要向s追加字符，然后跟这一组的长度
// 如果数组长度为 >= 10,则在chars数组中会被拆分为多个字符
// 设计一个使用常量额外空间的算法来解决此问题

// 思路，双指针法，slow指向已经处理过的数组的下一位，fast指向当前遍历的元素,遇到相同元素时处理逻辑，大于1个时需要拼接上具体的数量，
// 这里拼接需要有个反转
// 时间复杂度是O(n)，其中n是chars数组的长度。虽然有嵌套循环，但每个字符最多被访问常数次：外层while循环遍历所有字符，内层while循环找连续重复字符，数字拆分的while循环最多执行log10(n)次（常数级别）
// 空间复杂度是O(1)，只使用了常数级别的额外空间：slow和fast指针，以及count变量（最多占用log10(n)空间）

function compress(arr) {
    let slow = 0
    let fast = 0
    while (fast < arr.length) {
        let start = fast
        while (fast + 1 < arr.length && arr[fast + 1] === arr[fast]) {
            fast++
        }
        arr[slow] = arr[fast]
        slow++
        if (fast - start > 0) {
            let count = fast - start + 1
            let begin = slow
            while (count) {
                // 这里必须转为字符串
                arr[slow] = String(count % 10)
                count = Math.floor(count / 10)
                slow++
            }
            reverse(arr, begin, slow - 1)
        }
        fast++
    }
    return slow
}

function reverse(arr, left, right) {
    while (left < right) {
        [arr[left], arr[right]] = [arr[right], arr[left]];
        left++
        right--
    }
}

let chars = ["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b"]
chars = ["a","a","b","b","c","c","c"]
console.log(compress(chars));